/*
 * @lc app=leetcode.cn id=41 lang=java
 *
 * [41] 缺失的第一个正数
 */

// @lc code=start
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            if(nums[i] <= 0){
                nums[i] = n + 1;
            }
        }
        for(int i=0;i<n;i++){
            int num = Math.abs(nums[i]);
            if(num <= n){
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }

        for(int i=0;i<n;i++){
            if(nums[i] > 0){
                return i+1;
            }
        }
        
        return n+1;
    }
}
// @lc code=end

